#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2021-01-06 9:41 上午
# @Author  : yangdy
# @File    : 2021-01-06.399.除法求值
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # map
        keys = {}
        for ei in equations:
            for s in ei:
                if keys.get(s) is None:
                    keys[s] = len(keys)
        ll = len(keys)
        mm = [[-1.0 for i in range(ll)] for j in range(ll)]
        for i in range(len(equations)):
            x, y = keys[equations[i][0]], keys[equations[i][1]]
            mm[x][y], mm[y][x] = values[i], 1.0 / values[i]
            mm[x][x], mm[y][y] = 1.0, 1.0
        # bfs
        # ans = []
        # for qi in queries:
        #     if keys.get(qi[0]) is None or keys.get(qi[1]) is None:
        #         ans.append(-1.0)
        #     else:
        #         x, y = keys[qi[0]], keys[qi[1]]
        #         if mm[x][y] != -1.0:
        #             ans.append(mm[x][y])
        #             continue
        #         que, flag, i = [(x, 1.0)], True, 0
        #         while i < len(que) and flag:
        #             xx, dis = que[i]
        #             for yy in range(ll):
        #                 if yy != xx and mm[xx][yy] != -1.0:
        #                     if yy == y:
        #                         dis *= mm[xx][yy]
        #                         ans.append(dis)
        #                         flag = False
        #                         break
        #                     else:
        #                         dis *= mm[xx][yy]
        #                         mm[x][yy] = dis
        #                         que.append((yy, dis))
        #             if not flag:
        #                 break
        #             i += 1
        #         print(que)
        # return ans
        # floyd
        for z in range(ll):
            for x in range(ll):
                for y in range(ll):
                    if mm[x][z] != -1.0 and mm[z][y] != -1.0:
                        if mm[x][y] == -1.0:
                            mm[x][y] = mm[x][z] * mm[z][y]
        ans = []
        for qi in queries:
            if keys.get(qi[0]) is None or keys.get(qi[1]) is None:
                ans.append(-1.0)
            else:
                x, y = keys[qi[0]], keys[qi[1]]
                ans.append(mm[x][y])
        return ans


questions = [
    ([["a", "b"], ["b", "c"]], [2.0, 3.0], [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]),
    # [6.0, 0.5, -1.0, 1.0, -1.0]
    ([["a", "b"], ["b", "c"], ["bc", "cd"]], [1.5, 2.5, 5.0], [["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]]),
    # [3.75, 0.4, 5.0, 0.2]
    ([["x1", "x2"], ["x2", "x3"], ["x1", "x4"], ["x2", "x5"]], [3.0, 0.5, 3.4, 5.6],
     [["x2", "x4"], ["x1", "x5"], ["x1", "x3"], ["x5", "x5"], ["x5", "x1"], ["x3", "x4"], ["x4", "x3"], ["x6", "x6"],
      ["x0", "x0"]]),
    # [1.133, 16.7999, 1.5, 1.0, 0.0.595238, 2.26666, 0.441176, -1.0, -1.0]
]

work(questions, lambda q: Solution().calcEquation(q[0], q[1], q[2]))
